Computing by representing information in the form of DNA base sequences enjoys several potential advantages over silicon-based computing methods, due to the massive parallelism of the biochemical reactions on DNA molecules. These advantages include significantly enhanced processing speeds, significantly reduced energy consumption, and significantly greater storage capacity. DNA computing can solve problems intractable by conventional computing methods including but not limited to organization of mass evacuations, organization of response to invasion, supply chain problems, and computer chip assembly problems. As a result, there is tremendous interest in utilizing the computing capacity of DNA
A “nondeterministic polynomial optimization problem” is a class of optimization problems for which no efficient solution algorithm has been found. Tractable problems can be solved by computer algorithms that run in polynomial time; i.e., for a problem of size n, the time or number of steps needed to find the solution is a polynomial function of n. An optimization problem is called NP (nondeterministic polynomial) if its solution (if one exists) can be guessed and verified in polynomial time; nondeterministic means that no particular rule is followed to make the guess. Such “NP optimization problems” of any complexity thus pose a difficult computing issue, as previous attempts to solve using DNA-based computing require generation of the complete solution set. Thus, improved DNA-based computing methods for solving NP optimization problems are needed in the art.